package DailyPractice.Day14;

/**
 * @author lumin
 * @date 2022/05/10 19:18
 **/
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Num2  {

    //统计重复球数
    private static Map<Integer,Integer> countMap;
    //球的个数
    private static int N;
    //一共有多少种情况满足
    private static int sum;
    //唯一的编号有多少个
    private static int[] uninum;
    //每个数字的个数
    private static int[] numNum;
    //总共的唯一个数
    private static int sizeN;



    public static void main(String[] args) {

        Scanner sc =  new Scanner(System.in);
        countMap = new HashMap<Integer, Integer>();

        while (sc.hasNext())
        {
            int i;//索引

            sum = 0;
            //初始化map
            countMap.clear();

            //读取要读的楸树
            N = sc.nextInt();

            for(i = 0;i < N;i++)
            {
                int tmp = sc.nextInt();
                if(countMap.containsKey(tmp))
                {
                    //统计当前数字重复的个数
                    countMap.put(tmp,countMap.get(tmp) + 1);
                }
                else
                {
                    countMap.put(tmp,1);
                }
            }

            sizeN = countMap.size();

            uninum = new int[sizeN];
            numNum = new int[sizeN];

            i = 0;
            for(Integer item : countMap.keySet())
            {
                uninum[i] = item;
                i++;
            }
            Arrays.sort(uninum);

            for(i = 0;i < sizeN ;i++)
            {
                numNum[i] = countMap.get(uninum[i]);
            }

            findSum(0,0,1);

            System.out.println(sum);
        }

    }

    private static void findSum(int level,long addSum,long mulSum)
    {
        if(level == sizeN)
        {
            //这个就是幸运数字
            if(addSum > mulSum)
            {
                //如果加的数字大于乘起来的数字
                sum++;
            }
            return ;
        }
        //剪枝优化
        if (addSum !=0 && mulSum != 1 && mulSum > addSum ) return;

        for(int i = 0;i <= numNum[level]; i++)
        {
            //当前数字选择这么多个，然后将结果乘起来和加起来有多大
            findSum(level  + 1,
                    addSum + uninum[level] * i,
                    mulSum*myPow(uninum[level],i)
            );
        }
    }

    private static long myPow(int base,int index)
    {
        long ans = 1;
        for(int i = 0; i < index ; i++)
        {
            ans *= base;
        }
        return ans;
    }
}
